<!DOCTYPE html>
<html>
<head>
  <title>二叉搜索树可视化示例</title>
  <style>
    #canvas {
      border: 1px solid black;
    }
  </style>
</head>
<body>
  <h1>二叉搜索树可视化示例</h1>

  <div>
    <label for="inputSequence">输入序列:</label>
    <input type="text" id="inputSequence" placeholder="输入数字序列，以空格分隔" value="4 2 7 1 3 6 9">
  
    <!-- <input type="text" id="inputSequence" placeholder="输入数字序列，以空格分隔"> -->
    <button onclick="createBinarySearchTree()">创建二叉树</button>
  
  </div>

  <canvas id="canvas" width="800" height="400"></canvas>

  <script>
    // 获取 Canvas 元素
    const canvas = document.getElementById("canvas");
    const context = canvas.getContext("2d");

    class TreeNode {
      constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
      }
    }

    class BinarySearchTree {
      constructor() {
        this.root = null;
      }

      insert(value) {
        const newNode = new TreeNode(value);
        
        if (this.root === null) {
          this.root = newNode;
        } else {
          this.insertNode(this.root, newNode);
        }
      }

      insertNode(node, newNode) {
        if (newNode.value < node.value) {
          if (node.left === null) {
            node.left = newNode;
          } else {
            this.insertNode(node.left, newNode);
          }
        } else {
          if (node.right === null) {
            node.right = newNode;
          } else {
            this.insertNode(node.right, newNode);
          }
        }
      }

      // 先序遍历
      preorderTraversal(node, callback) {
        if (node !== null) {
          callback(node.value);
          this.preorderTraversal(node.left, callback);
          this.preorderTraversal(node.right, callback);
        }
      }

      // 绘制二叉搜索树
      draw() {
        context.clearRect(0, 0, canvas.width, canvas.height);
        this.drawNode(this.root, canvas.width / 2, 40, canvas.width / 4);
      }

      // 递归绘制节点和连接线
      drawNode(node, x, y, xOffset) {
        if (node !== null) {
          // 绘制节点
          context.strokeStyle = "black";
          context.fillStyle = "white";
          context.lineWidth = 2;
          context.beginPath();
          context.arc(x, y, 20, 0, 2 * Math.PI);
          context.fill();
          context.stroke();

          // 绘制节点值
          context.fillStyle = "black";
          context.font = "16px Arial";
          context.textAlign = "center";
          context.fillText(node.value, x, y + 6);

          // 绘制连接线和子节点
          const childOffset = xOffset / 2;
          if (node.left !== null) {
            context.beginPath();
            context.moveTo(x - 20, y + 20);
            context.lineTo(x - xOffset, y + 60);
            context.stroke();
            this.drawNode(node.left, x - xOffset, y + 80, childOffset);
          }
          if (node.right !== null) {
            context.beginPath();
            context.moveTo(x + 20, y + 20);
            context.lineTo(x + xOffset, y + 60);
            context.stroke();
            this.drawNode(node.right, x + xOffset, y + 80, childOffset);
          }
        }
      }
    }

    // // 创建二叉搜索树并插入节点
    // const bst = new BinarySearchTree();
    // // bst.insert
    // bst.insert(10);
    // bst.insert(5);
    // bst.insert(15);
    // bst.insert(3);
    // bst.insert(7);
    // bst.insert(12);
    // bst.insert(20);
    // bst.insert(21);
    // // 绘制二叉搜索树
    // bst.draw();

     // 获取输入序列的值
     function getInputSequence() {
      const inputSequence = document.getElementById("inputSequence").value;
      const sequenceArray = inputSequence.split(" ").map(Number);
      return sequenceArray;
    }

    // 创建二叉搜索树
    function createBinarySearchTree() {
      const sequenceArray = getInputSequence();
      const bst = new BinarySearchTree();
      sequenceArray.forEach(value => bst.insert(value));
      bst.draw();
    }
  </script>
</body>
</html>
